题目

题目描述

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
（1）tree的最高加分
（2）tree的前序遍历

输入格式

第1行：一个整数n（n＜30），为节点个数。

第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。

输出格式

第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。

第2行：n个用空格隔开的整数，为该树的前序遍历。

输入样例

1 2	5 5 7 1 2 10

输出样例

1 2	145 3 1 2 4 5

题解

一道入门的区间dp，当然，根据写法不同你还可以把它归类为树形dp或者记忆化搜索，其实都无所谓啦。
作为一道入门题，我们完全可以“显然”地做出来，但是在这里还是想和大家回顾下动态规划以及区间动规。

Q：dp特点是什么？
A：dp把原问题视作若干个重叠的子问题的逐层递进，每个子问题的求解过程都会构成一个“阶段”，在完成一个阶段后，才会执行下一个阶段。
Q：dp要满足无后效性，什么叫无后效性？
A：已经求解的子问题不受后续阶段的影响。

有人觉得dp很抽象，那是因为没有一步一步来想，直接听别人的结论，我们在这里以这道题为例，一步一步来推导。

首先，我们要做的就是设计状态，其实就是设计dp数组的含义，它要满足无后效性。
关注这个 左子树*右子树+根 我只要知道左子树分数和右子树分数和根的分数（已给出），不就可以了吗？管他子树长什么样！
所以，我们$f$数组存的就是最大分数，怎么存呢？
我们发现：子树是一个或多个节点的集合。
那么我们可不可以开一个$f[i][j]$来表示节点i到节点j成树的最大加分呢？可以先保留这个想法（毕竟暂时也想不到更好的了）。

如果这样话，我们就来设计状态转移方程。
按照刚刚的设计来说的话，我们的答案就是$f[1][n]$了，那么我们可以从小的子树开始，也就是len，区间长度。有了区间长度我们就要枚举区间起点，i为区间起点，然后就可以算出区间终点j。
通过加分二叉树的式子我们可以知道，二叉树的分取决于谁是根，于是我们就在区间内枚举根k。
特别的，$f[i][i]=a[i]$其中a[i]为第i个节点的分数。
因为是要求最大值，所以我们就可以设计出
$$f[i][j]=MAX(f[i][k-1]*f[k+1][j]+f[k][k])$$
于是乎，我们就自己设计出了一个dp过程，因为是顺着来的，所以很少有不成立的。

至于输出前序遍历，我们再设计一个状态$root[i][j]$来表示节点i到节点j成树的最大加分所选的根节点。
所以我们按照$根->左->右$的顺序递归输出即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 50;
typedef long long ll;
ll n;
ll f[MAXN][MAXN], root[MAXN][MAXN];

void print(ll l, ll r) {
	if (l > r)return;
	printf("%lld ", root[l][r]);
	if (l == r)return;
	print(l, root[l][r] - 1);
	print(root[l][r]+1,r);
}

int main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &f[i][i]),f[i][i-1]=1, root[i][i] = i;
	for (int len = 1; len < n; ++len) {
		for (int i = 1; i + len <= n; ++i) {
			int j = i + len;
			f[i][j] = f[i + 1][j] + f[i][i];//默认它的左子树为空，如果有的话，这肯定不是最优解
			root[i][j] = i;//默认从起点选根
			for (int k = i + 1; k < j; ++k) {
				if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k]) {
					f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
					root[i][j] = k;
				}
			}
		}
	}
	cout << f[1][n] << endl;
	print(1, n);
	return 0;
}